//
//  QuickSort.m
//  GLCodingInterview
//
//  Created by colyn on 2019/8/22.
//  Copyright © 2019 colyn. All rights reserved.
//

#import "QuickSort.h"

@implementation QuickSort

int changeCount = 0;//交换次数
int cycleCount = 0;//循环次数
bool isSort1Start = NO;
bool isSort2Start = NO;


+ (void)quickSort1Array:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex {
    if (isSort1Start == NO) {
        isSort1Start = YES;
        changeCount = 0;
        cycleCount = 0;
    }
    
    /* 数组元素个数位1或0时返回 */
    if (leftIndex >= rightIndex) return;
    
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    
    /* 比较基准数 */
    NSInteger key = [array[i] integerValue];
    cycleCount++;
    while (i < j) {
        /* 1、首先从j开始向左查找比基准数小的数*/
        while (i < j && [array[j] integerValue] >= key) {//如果比基准数大则继续查找
            cycleCount++;
            j--;
        }
        [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        changeCount++;
        [QuickSort LogTheArray:array];
        
        /* 2、然后从i开始往右边查找比基准数大的数 */
        while (i < j && [array[i] integerValue] <= key) {//如果比基准数小则继续查找
            cycleCount++;
            i++;
        }
        [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        changeCount++;
        [QuickSort LogTheArray:array];
    }
    
    /* 递归排序 */
    [self quickSort1Array:array leftIndex:leftIndex rightIndex:i-1];
    [self quickSort1Array:array leftIndex:i+1 rightIndex:rightIndex];
}

+ (void)quickSort2Array:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex {
    if (isSort2Start == NO) {
        isSort2Start = YES;
        changeCount = 0;
        cycleCount = 0;
    }
    if (leftIndex >= rightIndex) {
        return;
    }

    NSInteger pivot_index = [QuickSort Partition:array left:leftIndex right:rightIndex];
    [QuickSort quickSort2Array:array leftIndex:leftIndex rightIndex:pivot_index-1];
    [QuickSort quickSort2Array:array leftIndex:pivot_index+1 rightIndex:rightIndex];
}

+ (NSInteger)Partition:(NSMutableArray *)array left:(NSInteger)left right:(NSInteger)right {
    //这里每次都选择最左边一个元素作为基准
    NSInteger pivot = [array[left] integerValue];
    //tail为小于基准的子数组最后一个元素的索引
    NSInteger tail = left;
    cycleCount++;
    for (NSInteger i = left+1; i <= right; i++) {
        cycleCount++;
        if ([array[i] integerValue] <= pivot) {
            tail++;
            [array exchangeObjectAtIndex:tail withObjectAtIndex:i];
            changeCount++;
            [QuickSort LogTheArray:array];
        }
    }
    //tail存放的是最后一个小于基准的元素
    //tail+1则是大于基准的元素
    //最后把基准放到前一个子数组的后面，剩下的子数组即是大于基准的子数组
    [array exchangeObjectAtIndex:tail withObjectAtIndex:left];
    changeCount++;
    [QuickSort LogTheArray:array];
    return tail;//返回基准的索引
}

+ (void)LogTheArray:(NSArray *)array {
    NSMutableString *str = [NSMutableString stringWithCapacity:0];
    for (NSInteger i = 0; i < array.count; i++) {
        [str appendString:[NSString stringWithFormat:@"%ld",[array[i] integerValue]]];
        if (i != array.count-1) {
            [str appendString:@","];
        }
    }
    NSLog(@"循环次数：%03d,交换次数：%03d,排序后的数数组：%@",cycleCount,changeCount,str);
}

@end
